Płetwonurek

Limit pamięci: 32 MB

Płetwonurek do nurkowania używa butli, w której są dwa zbiorniki: z tlenem i z azotem. W zależności od czasu przebywania pod wodą i głębokości nurek potrzebuje różnych ilości tlenu i azotu. Płetwonurek ma do dyspozycji pewną liczbę butli. Każda butla charakteryzuje się wagą oraz objętością zawartego w niej tlenu i azotu. Do wykonania zadania nurek potrzebuje określonych ilości tlenu i azotu. Jaka jest najmniejsza sumaryczna waga butli, które nurek musi zabrać ze sobą, żeby mógł wykonać zadanie?

Przykład

Nurek ma do dyspozycji butli o następujących charakterystykach (odpowiednio: objętość tlenu w litrach, objętość azotu w litrach, waga butli w dekagramach):

3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

Jeżeli do wykonania zadania nurek potrzebuje litrów tlenu i litrów azotu, to musi zabrać ze sobą dwie butle o łącznej wadze , np. pierwszą i drugą lub czwartą i piątą.

Zadanie

Napisz program, który:

• wczytuje ze standardowego wejścia zapotrzebowanie nurka na tlen i azot, liczbę dostępnych butli oraz ich charakterystyki;
• oblicza najmniejszą sumaryczną wagę butli, które nurek musi zabrać ze sobą, żeby wykonać zadanie;
• zapisuje wynik na standardowe wyjście.

Uwaga: dany zestaw butli zawsze gwarantuje wykonanie zadania.

Wejście

W pierwszym wierszu standardowego wejścia znajdują się dwie liczby całkowite i , oddzielone pojedynczym odstępem, i . Są to, odpowiednio, ilości tlenu i azotu potrzebne do wykonania zadania.

Drugi wiersz pliku wejściowego zawiera tylko jedną liczbę , . Jest to liczba dostępnych butli. Kolejne wierszy zawiera charakterystyki butli. Wiersz zawiera trzy liczby całkowite , pooddzielane pojedynczymi odstępami (, , ). Są to kolejno: objętości tlenu i azotu w -tej butli oraz waga tej butli.

Wyjście

Twój program powinien zapisać jedną liczbę całkowitą w pierwszym i jedynym wierszu standardowego wyjścia. Tą liczbą powinna być najmniejsza sumaryczna waga butli, które nurek musi zabrać ze sobą, żeby mógł wykonać zadanie.

Przykład

Dla danych wejściowych:

5 60
5
3 36 120
10 25 129
5 50 250
1 45 130
4 20 119

poprawną odpowiedzią jest:

249